package org.hhchat.others.erp;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by OovEver on 2017/5/24.
 */
public class Main4 {
    static boolean judge(int []nums,int m){
        int n=nums.length;
        if(n==0||m==0)
            return false;
        Arrays.sort(nums);


        if(Arrays.binarySearch(nums,m)>0)
            return true;
//        初始化栈
        Stack<Integer> stack=new Stack<Integer>();
        int sumCur=nums[0];
        int now=0;
        stack.push(0);
        now=stack.peek();
        while (true){
            if(sumCur<m){
                now++;
                if(now<n){
                    stack.push(now);
                    sumCur+=nums[now];
                }else if(stack.empty()){
                    return false;
                }else {
                    now=stack.peek();
                    stack.pop();
                    sumCur-=nums[now];
                }

            }else if(sumCur>m){
                // 出口：只有一个值，并且还大于要求的和，那就没有答案了
                if(stack.size()<2)
                    return false;
                else {
                    sumCur-=nums[stack.peek()];
                    stack.pop();
                    sumCur-=nums[stack.peek()];
                    now=stack.peek();
                    stack.pop();

                }

            }else{
                return true;
            }
        }




    }
    public static void main(String[] args) {
//
//        int n,m;
//        Scanner sc=new Scanner(System.in);
//        n=sc.nextInt();
//        m=sc.nextInt();
//        int []nums=new int[n];
//        int sumNum=0;
//        for(int i=0;i<n;i++){
//            nums[i]=sc.nextInt();
//            sumNum+=nums[i];
//        }
//        boolean flag=false;
//        int sum=m;
//        int len=2;
//        while (sum<=sumNum&&!flag){
//            flag=judge(nums,sum);
//            sum*=len;
//            len++;
//        }
//        System.out.println(flag);
        int n,m;
//        Scanner sc=new Scanner(System.in);
//        n=sc.nextInt();
//        m=sc.nextInt();
//        int []nums=new int[n];
        m=120;
        int[] nums={1,3,5,7,3,6,8,4,1,3,1,3,8,6,1,3,1,3,8,4,1,3,3,1};
        int sumNum=0;
        for(int i=0;i<nums.length;i++){
//            nums[i]=sc.nextInt();
            sumNum+=nums[i];
        }
        boolean flag=false;
        int sum=m;
        int len=2;
        while (sum!=0&&sum<=sumNum&&!flag){
            flag=judge(nums,sum);
            sum*=len;
            len++;
        }
        System.out.print(flag);
    }
}
